package com.caochenlei.tree.heap;

import java.util.Comparator;

public class BinaryHeap<E> {
    private E[] elements;                               //存储堆中所有元素
    private int size;                                   //存储堆中元素个数
    private Comparator<E> comparator;                   //存储一个比较对象
    private static final int DEFAULT_CAPACITY = 16;     //存储默认容量大小

    public BinaryHeap(E[] elements, Comparator<E> comparator) {
        if (elements == null) {
            this.size = 0;
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
            this.comparator = comparator;
        } else {
            this.size = elements.length;
            this.elements = (E[]) new Object[Math.max(elements.length, DEFAULT_CAPACITY)];
            this.comparator = comparator;
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            heapify();
        }
    }

    public BinaryHeap(E[] elements) {
        this(elements, null);
    }

    public BinaryHeap(Comparator<E> comparator) {
        this(null, comparator);
    }

    public BinaryHeap() {
        this(null, null);
    }

    //确保堆容量可用
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        int newCapacity = oldCapacity + (oldCapacity / 2);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

    //比较两元素大小
    private int compare(E e1, E e2) {
        return comparator != null ? comparator.compare(e1, e2) : ((Comparable<E>) e1).compareTo(e2);
    }

    //获取堆元素个数
    public int size() {
        return size;
    }

    //判断堆是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //清空堆所有元素
    public void clear() {
        //需循环释放引用
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    //获取堆顶的元素
    public E get() {
        //判断堆是否为空
        if (isEmpty()) {
            return null;
        }
        return elements[0];
    }

    @Override
    public String toString() {
        String s = "";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            sb.append(elements[i] + ", ");
        }
        if (!isEmpty()) {
            s = sb.substring(0, sb.length() - 2);
        }
        return "BinaryHeap{elements=[" + s + "]}";
    }

    //向堆中追加元素
    public void add(E e) {
        //确保容量
        ensureCapacity(size + 1);
        //添加元素
        elements[size++] = e;
        //上滤操作
        siftUp2(size - 1);
    }

    private void siftUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (compare(elements[index], elements[parentIndex]) > 0) {
                E temp = elements[index];
                elements[index] = elements[parentIndex];
                elements[parentIndex] = temp;
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    private void siftUp2(int index) {
        E node = elements[index];
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (compare(node, elements[parentIndex]) > 0) {
                elements[index] = elements[parentIndex];
                index = parentIndex;
            } else {
                break;
            }
        }
        elements[index] = node;
    }

    //删除并返回堆顶
    public E remove() {
        //判断堆是否为空
        if (isEmpty()) {
            return null;
        }
        //保存根结点元素
        E root = elements[0];
        //取最后元素索引
        int lastIndex = --size;
        //替换根结点元素
        elements[0] = elements[lastIndex];
        //删除最后的元素
        elements[lastIndex] = null;
        //下滤操作
        siftDown2(0);
        //返回元素
        return root;
    }

    private void siftDown(int index) {
        //index < (size / 2)：此判断代表的都是非叶子结点，叶子结点是不需要进行下滤
        while (index < (size / 2)) {
            int leftChildIndex = (index * 2) + 1;   //当前结点的左子结点下标
            int rightChildIndex = (index * 2) + 2;  //当前结点的右子结点下标

            //找到左右子结点中最大的那个
            int childIndex = leftChildIndex;
            if (rightChildIndex < size && compare(elements[rightChildIndex], elements[leftChildIndex]) > 0) {
                childIndex = rightChildIndex;
            }

            //当前结点和最大子结点哪个大
            if (compare(elements[index], elements[childIndex]) < 0) {
                E temp = elements[index];
                elements[index] = elements[childIndex];
                elements[childIndex] = temp;
                index = childIndex;
            } else {
                break;
            }
        }
    }

    private void siftDown2(int index) {
        E node = elements[index];
        //index < (size / 2)：此判断代表的都是非叶子结点，叶子结点是不需要进行下滤
        while (index < (size / 2)) {
            int leftChildIndex = (index * 2) + 1;   //当前结点的左子结点下标
            int rightChildIndex = (index * 2) + 2;  //当前结点的右子结点下标

            //找到左右子结点中最大的那个
            int childIndex = leftChildIndex;
            if (rightChildIndex < size && compare(elements[rightChildIndex], elements[leftChildIndex]) > 0) {
                childIndex = rightChildIndex;
            }

            //当前结点和最大子结点哪个大
            if (compare(node, elements[childIndex]) < 0) {
                elements[index] = elements[childIndex];
                index = childIndex;
            } else {
                break;
            }
        }
        elements[index] = node;
    }

    //替换并返回堆顶
    public E replace(E element) {
        E root = null;
        if (size == 0) {
            root = element;         //保存根结点元素
            elements[0] = element;  //替换根结点元素
            size++;                 //元素数量应加一
        } else {
            root = elements[0];     //保存根结点元素
            elements[0] = element;  //替换根结点元素
            siftDown(0);      //根结点需要下滤
        }
        return root;
    }

    //堆化算法
    private void heapify() {
        //第一种堆化算法：自上而下的上滤，时间复杂度大，不用
        //for (int i = 1; i < size; i++) {
        //    siftUp(i);
        //}

        //第二种堆化算法：自下而上的下滤，时间复杂度小，采取
        //i < (size / 2)：此判断代表的都是非叶子结点，叶子结点是不需要进行下滤
        for (int i = (size / 2) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }
}
